#include <bits/stdc++.h>
using namespace std;

/*
3440. 重新安排会议得到最多空余时间 II
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 一个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外，且会议之间需要保持互不重叠。

注意：重新安排会议以后，会议之间的顺序可以发生改变。

 

示例 1：

输入：eventTime = 5, startTime = [1,3], endTime = [2,5]

输出：2

解释：



将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]

输出：7

解释：



将 [0, 1] 的会议安排到 [8, 9] ，得到空余时间 [0, 7] 。

示例 3：

输入：eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]

输出：6

解释：



将 [3, 4] 的会议安排到 [8, 9] ，得到空余时间 [1, 7] 。

示例 4：

输入：eventTime = 5, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]

输出：0

解释：

活动中的所有时间都被会议安排满了。

 

提示：

1 <= eventTime <= 109
n == startTime.length == endTime.length
2 <= n <= 105
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。
*/

// 法一
class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size(), res = 0;
        // 同时处理从左到右和从右到左的情况
        for (int i = 0, t1 = 0, t2 = 0; i < n; i++) {
            // 计算移除会议i后，左右两侧会议形成的新空闲区间
            int left1 = i == 0 ? 0 : endTime[i - 1];
            int right1 = i == n - 1 ? eventTime : startTime[i + 1];
            
            // 如果会议i的时长 <= 左侧已知最大非相邻空闲时间t1
            // 则可以将会议i平移到左侧，此时新空闲区间为right1 - left1
            if (endTime[i] - startTime[i] <= t1) {
                res = max(res, right1 - left1);
            }
            
            // 更新左侧最大非相邻空闲时间（包含当前会议左侧的空闲时间）
            t1 = max(t1, startTime[i] - (i == 0 ? 0 : endTime[i - 1]));

            // 不移除会议i，仅计算合并相邻空闲区间后的剩余空间
            res = max(res, right1 - left1 - (endTime[i] - startTime[i]));

            // 对称处理从右到左的情况（i对应n-i-1）
            int left2 = i == n - 1 ? 0 : endTime[n - i - 2];
            int right2 = i == 0 ? eventTime : startTime[n - i];
            
            // 如果对称会议n-i-1的时长 <= 右侧已知最大非相邻空闲时间t2
            // 则可以将会议n-i-1平移到右侧，此时新空闲区间为right2 - left2
            if (endTime[n - i - 1] - startTime[n - i - 1] <= t2) {
                res = max(res, right2 - left2);
            }
            
            // 更新右侧最大非相邻空闲时间（包含对称会议右侧的空闲时间）
            t2 = max(t2, (i == 0 ? eventTime : startTime[n - i]) - endTime[n - i - 1]);
        }
        return res;
    }
};

// 法二
class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        // q[i] 标记会议i是否可以被平移到左侧或右侧的空闲区间
        vector<bool> q(n);
        
        // 第一阶段：预处理每个会议是否可以被平移
        // 从左到右扫描，记录左侧最大非相邻空闲时间t1
        // 从右到左扫描，记录右侧最大非相邻空闲时间t2
        for (int i = 0, t1 = 0, t2 = 0; i < n; i++) {
            // 如果当前会议时长 <= 左侧最大非相邻空闲时间t1
            // 则该会议可以被平移到左侧，标记为true
            if (endTime[i] - startTime[i] <= t1) {
                q[i] = true;
            }
            // 更新左侧最大非相邻空闲时间
            t1 = max(t1, startTime[i] - (i == 0 ? 0 : endTime[i - 1]));

            // 对称处理右侧情况：检查对称会议n-i-1是否可以被平移到右侧
            if (endTime[n - i - 1] - startTime[n - i - 1] <= t2) {
                q[n - i - 1] = true;
            }
            // 更新右侧最大非相邻空闲时间
            t2 = max(t2, (i == 0 ? eventTime : startTime[n - i]) - endTime[n - i - 1]);
        }

        // 第二阶段：计算最大空闲时间
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 计算移除会议i后，其左右两侧会议形成的空闲区间
            int left = i == 0 ? 0 : endTime[i - 1];
            int right = i == n - 1 ? eventTime : startTime[i + 1];
            
            // 如果会议i可以被平移，则合并后的空闲区间为right-left
            // 否则，合并后的空闲区间需要减去会议i的时长
            if (q[i]) {
                res = max(res, right - left);
            } else {
                res = max(res, right - left - (endTime[i] - startTime[i]));
            }
        }
        return res;
    }
};